package leetcode._07_贪心;

import org.junit.Test;

/**
 * @author pppppp
 * @date 2022/3/17 14:37
 * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 判断你是否能够到达最后一个下标。
 * <p>
 * 示例 1：
 * 输入：nums = [2,3,1,1,4]
 * 输出：true
 * 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
 * <p>
 * 示例 2：
 * 输入：nums = [3,2,1,0,4]
 * 输出：false
 * 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
 */
public class _55_跳跃游戏 {
    @Test
    public void T_0() {
        int[][] nums = {{1, 2, 0, 1}, {2, 0, 0}, {2, 3, 1, 1, 4}, {3, 2, 1, 0, 4}};
        boolean[] ans = {true, true, true, false};
        for (int i = 0; i < nums.length; i++) {
            // System.out.println(canJump_0(nums[i]) == ans[i]);
            System.out.println(canJump_1(nums[i]) == ans[i]);
        }

    }

    /*维护一个当前能达到的所有位置 若无法继续前进就false*/
    public boolean canJump_1(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        if (nums[0] == 0) {
            return false;
        }
        int maxIndex = 0;
        for (int i = 0; i < nums.length ; i++) {
            if(i >  maxIndex){
                return false;
            }
            maxIndex = Math.max(maxIndex,i + nums[i]);
            if (maxIndex >= nums.length - 1) {
                return true;
            }
        }
        return true;
    }

    /*0.只要能跳过所有的0则能通过*/
    public boolean canJump_0(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        if (nums[0] == 0) {
            return false;
        }

        for (int i = 1; i < nums.length - 1; i++) {
            if (nums[i] + i >= nums.length - 1) {
                return true;
            }
            if (nums[i] == 0) {
                int pre = i - 1;
                while (pre >= 0) {
                    if (nums[pre] > i - pre) {
                        break;
                    }
                    pre--;
                }
                if (pre == -1) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean dfs(int i, int[] nums) {
        if (i >= nums.length - 1) {
            return true;
        }
        if (nums[i] == 0) {
            return false;
        }
        for (int j = nums[i]; j > 0; j--) {
            if (dfs(i + j, nums)) {
                return true;
            }
        }
        return false;
    }
}
